A computer network is a geographically distributed collection of interconnected subnetworks, such as local area networks (LAN), that transport data between network nodes. As used herein, a network node is any device adapted to send and/or receive data in the computer network. Thus, in the context of this disclosure, the terms “node” and “device” may be used interchangeably. The network topology is defined by an arrangement of network nodes that communicate with one another, typically through one or more intermediate network nodes, such as routers and switches. In addition to intra-network communications between network nodes located in the same network, data also may be exchanged between nodes located in different networks. To that end, an “edge device” located at the logical outer-bound of a first computer network may be adapted to send and receive data with an edge device situated in a neighboring (i.e., adjacent) network. Inter-network and intra-network communications are typically effected by exchanging discrete packets of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how network nodes interact with each other.
Each data packet typically comprises “payload” data prepended (“encapsulated”) by at least one network header formatted in accordance with a network communication protocol. The network headers include information that enables network nodes to efficiently route the packet through the computer network. Often, a packet's network headers include a data-link (layer 2) header, an internetwork (layer 3) header and a transport (layer 4) header as defined by the Transmission Control Protocol/Internet Protocol (TCP/IP) Reference Model. The TCP/IP Reference Model is generally described in more detail in Section 1.4.2 of the reference book entitled Computer Networks, Fourth Edition, by Andrew Tanenbaum, published 2003, which is hereby incorporated by reference as though fully set forth herein.
A data packet may originate at a source node and subsequently “hop” from node to node along a logical data path until it reaches its destination. The network addresses defining the logical data path of a data flow are most often stored as Internet Protocol (IP) addresses in the packet's internetwork header. IP addresses are typically formatted in accordance with the IP Version 4 (IPv4) protocol, in which network nodes are addressed using 32 bit (four byte) values. Specifically, the IPv4 addresses are denoted by four numbers between 0 and 255, each number usually delineated by a “dot.” A subnetwork may be assigned to an IP address space containing a predetermined range of IPv4 addresses. For example, an exemplary subnetwork may be allocated the address space 128.0.10.*, where the asterisk is a wildcard that can differentiate up to 254 individual nodes in the subnetwork (0 and 255 are reserved values). In this case, a first node in the subnetwork may be assigned to the IP address 128.0.10.1, whereas a second node may be assigned to the IP address 128.0.10.2.
Although IPv4 is prevalent in most networks today, IP Version 6 (IPv6) has been introduced to increase the length of an IP address to 128 bits (16 bytes), thereby increasing the number of available IP addresses. For purposes of discussion, IP addresses will be represented as IPv4 addresses hereinafter, although those skilled in the art will appreciate that IPv6 or other layer-3 address formats alternatively may be used in the illustrative embodiments described herein.
A subnetwork is often associated with a subnet mask that may be used to select a set of contiguous high-order bits from IP addresses within the subnetwork's allotted address space. A subnet mask length indicates the number of contiguous high-order bits selected by the subnet mask, and a subnet mask length of N bits is hereinafter represented as /N. The subnet mask length for a given subnetwork is typically selected based on the number of bits required to distinctly address nodes in that subnetwork. Subnet masks and their uses are more generally described in Chapter 9 of the reference book entitled Inter-connections Second Edition, by Radia Perlman, published January 2000, which is hereby incorporated by reference as though fully set forth herein.
By way of example, assume an exemplary subnetwork is assigned the IP address space 128.0.10.4, and the subnetwork contains two addressable (reachable) network nodes. In this case, 30 address bits are needed to address the subnetwork 128.0.10.4, and the remaining two address bits may be used to distinctly address either of the two nodes in the subnetwork. In this case, the subnetwork may be associated with a subnet mask length of /30 (i.e., its subnet mask equals 0xFFFFFFFC in hexadecimal) since only the first 30 most-significant bits of an IP address are required to uniquely address subnetwork 128.0.10.4. As used herein, an “address prefix” is defined as the result of applying a subnet mask to a network address. An address prefix therefore specifies a range of network addresses in a subnetwork, and a /32 address prefix corresponds to a particular network address. A “route” is defined herein as an address prefix and its associated path attributes.
Two or more address prefixes may be aggregated if they specify contiguous ranges of network addresses or if one prefix's range of addresses is a superset of the other prefixes'. For example, consider the address prefixes 128.52.10.0 /24 and 128.52.10.5 /30. Since the prefix 128.52.10.0 /24 includes every IP address in the subnetwork described by the prefix 128.52.10.5 /30, the two prefixes may be aggregated as a single prefix 128.52.10.0 /24. By way of further example, the prefixes 128.52.10.0 /25 and 128.52.10.128 /25 respectively specify contiguous ranges of IP addresses 128.52.10.0-127 and 128.52.10.128-255. Accordingly, these two prefixes may be aggregated as a single address prefix 128.52.10.0 /24 which contains both IP address ranges.
Prefix aggregation (or “route aggregation”) is especially useful when installing routes in a forwarding information base (FIB). As noted, IP-based data packets include source and destination IP addresses that identify the packet's sending and receiving nodes. Packet-forwarding determinations are typically made based on the value of the packet's destination IP address. Specifically, the destination address may be parsed to determine the packet's next hop. FIG. 1A illustrates an exemplary IP-based FIB 100 that may be used to parse a packet's destination IP address to determine the packet's next hop. For purposes of illustration and description, the exemplary FIB is arranged as a 4×8 multiway trie (MTRIE), although those skilled in the art will understand that other searchable data structures alternatively may be employed. Moreover, non-IP-based FIBs also may be employed when a packet's next-hop information can be determined based on, e.g., the value of a layer-2 identifier, such as virtual-circuit identifier or the like.
The MTRIE is a searchable tree structure having four levels 110-140, where the top-most level is a 256-entry “root” vector 110. Each entry 112 in the root vector is indexed to correspond to a particular value between 0 and 255. To perform an address lookup in the MTRIE, the first 8 most-significant bits of a packet's destination IP address are used to uniquely index a root-vector entry 112. The indexed entry 112 may store a pointer to a second-level vector 120, a pointer to the packet's next-hop information 150 or a predetermined null value. If the indexed entry references the packet's next-hop information, the packet may be forwarded to its next-hop destination. However, if the indexed entry references a second-level vector 120, the next 8 most-significant bits of the destination IP address are used to index an entry 122 in the second-level vector.
The indexed second-level vector entry 122 may reference a third-level vector 130, or may reference the location of the packet's next-hop forwarding information 150. In the former case, an entry 132 in the referenced third-level vector 130 may be indexed by the next 8 most-significant bits of the packet's destination IP address. The indexed entry 132, in turn, may store a pointer that references a fourth-level vector 140. Because the MTRIE contains only four levels, the 8 least-significant bits of the destination IP address are used to locate a matching fourth-level entry 142, which stores a pointer to the packet's next-hop information 150. In this manner, the MTRIE is “walked,” eight bits at a time, until the packet's next-hop information 150 is located. As shown, the exemplary 4×8 MTRIE contains entries 142 that reference next-hop information 150a and 150b for the destination IP addresses 10.1.1.1 /32 and 10.1.1.2 /32.
FIG. 1B illustrates the exemplary FIB 100 where the destination IP addresses 10.1.1.1 /32 and 10.1.1.2 /32 have been aggregated as a single address prefix 10.1.1.0 /24. In this embodiment, the FIB is configured to locate the same next-hop information 160 for any packet whose destination IP address begins with 10.1.1. By aggregating the prefixes in this manner, the fourth-level vector 140 is not needed in the MTRIE, and thus less memory may be allocated for the FIB than in the embodiment of FIG. 1A. Further, fewer MTRIE lookups need to be performed to locate the packet's next-hop information. In short, route aggregation reduces the number of address prefixes stored in the FIB and enables the FIB to be searched faster while consuming less memory.
Multi-Area Networks
A computer network may contain smaller groups of one or more subnetworks which may be managed as separate autonomous systems. As used herein, an autonomous system (AS) is broadly construed as a collection of interconnected network nodes under a common administration. Often, the AS is managed by a single administrative entity, such as a company, an academic institution or a branch of government. For instance, the AS may operate as an enterprise network, a service provider or any other type of network or subnetwork.
The AS may contain one or more edge devices (or “autonomous system border routers” (ASBR)), having peer connections to edge devices located in adjacent networks or subnetworks. Thus, packets enter or exit the AS through an appropriate ASBR. The AS may be logically partitioned into a plurality of different “routing areas.” One routing area is usually designated as a “backbone area” (Area 0) through which nodes in other routing areas can communicate.
Network nodes located in the same routing area generally share routing information and network-topology information using an “interior gateway” routing protocol (IGP), such as a link-state protocol. Examples of conventional link-state protocols include, but are not limited to, the Open Shortest Path First (OSPF) protocol and the Intermediate-System-to-Intermediate-System (IS-IS) protocol. The OSPF protocol is described in more detail in Request for Comments (RFC) 2328, entitled OSPF Version 2, dated April 1998, which is publicly available through the Internet Engineering Task Force (IETF) and is hereby incorporated by reference in its entirety. The IS-IS protocol is described in more detail in the IETF publication RFC 1195, entitled Use of OSI IS-IS for Routing in TCP/IP and Dual Environments, dated December 1990, which is incorporated herein by reference in its entirety.
Conventional link-state protocols typically employ link-state advertisements (LSA) for exchanging routing and topology information between a set of interconnected intermediate network nodes, i.e., routers and switches. In fact, different types of LSAs may be used to communicate the routing and topology information. For example, the OSPF version 2 specification (RFC 2328) defines the following types of LSAs: Router, Network, Summary and AS-External LSAs. Router and Network LSAs are used to propagate link information within a routing area. Specifically, Router LSAs advertise router-interface links (i.e., links connected to routers) and their associated cost values, whereas Network LSAs advertise network-interface links (i.e., links connected to subnetworks) and their associated cost values within the routing area.
Summary and AS-External LSAs are used to disseminate routing information between routing areas. A Summary LSA is typically generated by an area border device, such as an area border router (ABR), located at the boundary of different routing areas. First, the ABR receives LSAs in a first routing area. The ABR “summarizes” routes advertised in the LSAs by aggregating the routes where possible. Next, the ABR stores the summarized routes in a Summary LSA, which it then advertises in a second routing area. In this way, nodes in the second area are made aware of routes that can be reached through the ABR. The OSPF specification defines a “type 3” and “type 4” Summary LSA. The type-3 Summary LSA advertises routes to reachable subnetworks; the type-4 Summary LSA advertises routes to reachable ASBRs. An AS-External LSA stores a list of reachable inter-AS (“external”) routes, i.e., located outside of the AS. The AS-External LSA is typically generated by an ASBR and is propagated throughout the AS to identify which external routes can be reached through the advertising ASBR. Unlike Summary LSAs, routes stored in an AS-External LSA are generally not aggregated.
Although OSPF LSAs are described herein for purposes of discussion, those skilled in the art will understand that other link-state protocols may utilize different LSA formats. For instance, IS-IS link-state packets (LSP) generally advertise type-length-value (TLV) tuples, where each TLV may be configured to store routing or topology information for distribution within a single routing area, across different routing areas, or across AS boundaries. Those skilled in the art will also understand that routing and topology information may be disseminated in other types of OSPF LSAs besides those described above. For example, “opaque” LSAs provide an extensible LSA format for use with the OSPF protocol and are generally described in more detail in the IETF publication RFC 2370, entitled The OSPF Opaque LSA Option, published July 1998, which is hereby incorporated by reference as though fully set forth herein.
Each network node in a routing area typically maintains its own link-state data-base (LSDB). The LSDB is configured to store routing and topology information advertised with the node's routing area. Because an ABR (by definition) participates in multiple routing areas, each ABR maintains a separate LSDB for each of its routing areas. In operation, network nodes in a routing area “flood” LSAs to ensure that every node in that area populates its LSDB with the same set of routing and topology information. In this way, the area's network nodes share a consistent “view” of the network. Moreover, because Summary and AS-External LSAs are advertised across area boundaries, LSDBs of nodes located in different routing areas can maintain consistent sets of inter-area and inter-AS routing information.
Since consistent sets of intra-area, inter-area and inter-AS routing information are usually distributed among network nodes in an AS, the nodes can calculate consistent sets of “best paths” through the AS, e.g., using conventional shortest path first (SPF) calculations or other routing computations. A calculated best path corresponds to a preferred data path for transporting data between a pair of source and destination nodes. The preferred path may be an intra-area, inter-area or inter-AS data path, depending on the locations of the source and destination nodes. For inter-area routes, e.g., between ASBRs, the data may be transported over the preferred path using a tunneling mechanism, such as the Multi-Protocol Label Switching (MPLS) protocol. The MPLS protocol and its operation are described in more detail in Chapter 7 of the reference book entitled IP Switching and Routing Essentials, by Stephen Thomas, published 2002, which is hereby incorporated by reference as though fully set forth herein.
FIG. 2 illustrates an exemplary AS 200 having a plurality of different routing areas 210-230. In this exemplary AS configuration, a “backbone” routing area 210 (Area 0) is coupled to a first routing area 220 (Area 1) and second routing area 230 (Area 2). Thus, network nodes located in the areas 210 and 220 can send inter-area communications via the backbone area 210. To that end, each of the routing areas 220 and 230 includes at least one ABR 250 that can communicate in the backbone area, such as ABR1 (i.e., located between Areas 0 and 1) and ABR2 (i.e., located between Areas 0 and 2). The routing areas 220 and 230 also may include one or more ASBRs 240 adapted to send and receive inter-AS communications. For instance, the exemplary AS 200 may be configured as a RFC-2547 provider network that is coupled to a plurality of neighboring customer sites, as set forth in the IETF publication RFC 2547, entitled BGP/MPLS VPNs, by E. Rosen et al., published March 1999, which is hereby incorporated by reference in its entirety. In such an embodiment, the ASBRs 240 may be provider edge (PE) devices that provide virtual private network (VPN) connectivity between customer edge (CE) devices located in remote customer sites.
In accordance with a known technique for forwarding data across multiple routing areas, data may be tunneled from an ASBR1 located in Area 1 to an ASBR2 located in Area 2. An optimal end-to-end data path 205 between these ASBRs may be calculated, e.g., based on the result of an SPF calculation. Initially, ASBR1 forwards a data packet across Area 1 to ABR1. The packet may include a three-level MPLS label stack 260 having a top-most IGP label 262, an edge-device label 264 and a bottom-most VPN label 290. The IGP label 262 is used within Area 1 to identify ABR1 as the packet's destination within Area 1. The edge-device label 264 is used within Area 1 to identify ASBR2 as the packet's destination within AS 200. The VPN label 290 identifies to which customer site ASBR2 should forward the packet after the packet has traversed the entire length of data path 205.
After receiving the data packet, ABR1 performs a label-lookup operation based on the value of the edge-device label 264 to determine the packet's next destination within backbone Area 0. In this case, ABR1 determines that the packet should be forwarded to ABR2, i.e., the next ABR situated along data path 205. Before forwarding the packet, ABR1 may replace (or modify) the packet's MPLS label stack 260 with a new label stack 270 having an IGP label 272, an edge-device label 274 and the VPN label 290. The IGP label 272 is used within Area 0 to identify ABR2 as the packet's destination within Area 0. The edge-device label 274 is used within Area 0 to identify ASBR2 as the packet's destination within AS 200. The VPN label 290 is not changed. ABR2 receives the packet and, based on the value of the received edge-device label 274, determines that ASBR2 is the packet's destination within Area 2. Accordingly, ABR2 replaces the packet's label stack with a two-level MPLS label stack 280 having a top-most IGP label 282 that identifies ASBR2 as the packet's destination in Area 2 and a bottom-most VPN 290 that identifies to which customer site ASBR2 should forward the packet.
The IGP labels 262, 272 and 282 are usually distributed within their respective routing areas using a conventional label distribution protocol, such as the Resource Reservation Protocol (RSVP), Label Distribution Protocol (LDP) or the like. The VPN label 290 is distributed among the fully-meshed set of ASBRs 240, e.g., using Multi-Protocol BGP (MP-BGP) or any other well known protocol that may be adapted to distribute VPN labels. Although conventional protocols are typically used for distributing IGP and VPN labels, there currently is not a standardized protocol for distributing edge-device labels in multi-area networks.
U.S. Pat. Nos. 6,473,421 and 6,603,756, both entitled Hierarchical Label Switching Across Multiple OSPF Areas, by Daniel C. Tappan, respectively published Oct. 29, 2002 and Aug. 5, 2003, and which are both hereby incorporated by reference in their entireties, teach one technique that may be used to distribute edge-device labels across routing areas. According to this known technique, the edge-device labels may be communicated across OSPF routing areas using AS-External LSAs. More particularly, the AS-External LSAs store mappings of ASBR addresses with their corresponding edge-device label values. Since the AS-External LSAs are disseminated throughout all routing areas in the AS, the ASBR addresses and their edge-device labels can be communicated to each ABR and ASBR.
Although the above-noted edge-device label distribution technique works well, it requires certain AS configurations. For instance, because ASBR addresses are advertised in AS-External LSAs, Summary LSAs are not used to advertise the ASBR addresses. As a result, ASBR routes are not aggregated, and thus every ASBR route has to be separately installed in the network devices' FIBs and LSDBs. This inability to summarize the ASBR addresses may result in redundant FIB and LSDB entries (that otherwise could have been combined using route aggregation). The redundant FIB and LSDB entries, in turn, may increase memory consumption in the ABRs and ASBRs and further may increase their latencies of performing FIB lookups and routing computations, such as SPF calculations.
In addition, use of AS-External LSAs to advertise ASBR addresses also may lead to undesired LSA “looping” between area boundaries. Unlike Summary LSAs which are of area scope, the AS-External LSAs are flooded across multiple routing areas. As such, an AS-External LSA may originate in a first routing area, propagate out of that area, then eventually loop back into the first area. Such looping may lead to unnecessary consumption of network bandwidth and/or processing resources.